#include <vector>
#include <iostream>
using namespace std;

bool isPostOrder(const vector<int> &vec, const int &begin, const int &end) {
  if (vec.size() == 0 || (size_t)begin >= vec.size() || (size_t)end >= vec.size() || begin > end)
    return false;
  if (end == begin)
    return true;

  int mid = begin;
  while (vec[mid] < vec[end]) {
    ++mid;
  }
  for (auto i = mid; i < end; ++i) {
    if (vec[i] < vec[end])
      return false;
  }
  return isPostOrder(vec, begin, mid - 1) && isPostOrder(vec, mid, end - 1);
}

bool isPreOrder(const vector<int> &vec, const int &begin, const int &end) {
  if (vec.size() == 0 || (size_t)begin >= vec.size() || (size_t)end >= vec.size() || begin > end)
    return false;
  if (end == begin)
    return true;

  int mid = begin + 1;
  while (vec[mid] < vec[begin]) {
    ++mid;
  }
  for (auto i = mid; i <= end; ++i) {
    if (vec[i] < vec[begin]) {
      return false;
    }
  }
  return isPreOrder(vec, begin + 1, mid - 1) && isPreOrder(vec, mid, end);
}

int main() {
  vector<int> vec = {5, 7, 6, 9, 11, 10, 8};
  cout << isPostOrder(vec, 0, vec.size() - 1) << " expected: 1" << endl;

  vec = {7, 4, 6, 5};
  cout << isPostOrder(vec, 0, vec.size() - 1) << " expected: 0" << endl;

  vec = {8, 6, 5, 7, 10, 9, 11};
  cout << isPreOrder(vec, 0, vec.size() - 1) << " expected: 1" << endl;

  vec = {8, 6, 5, 7, 10, 11, 9};
  cout << isPreOrder(vec, 0, vec.size() - 1) << " expected: 0" << endl;

  return 0;
}
